/*
	线性表中元素递增且顺序存储与计算机内(即为有序的顺序表),设计一个算法用尽可能的少的时间找出数值为x的值，并和其直接后继元素呼唤,
	若x不存在线性表中插入x并且不改变线性表递增的特性.
	思路：对折查询
*/
#include<stdio.h>
#include<malloc.h>
#include"..\Sequence_List\zyf_SqList.h"


void SearchExchangeInsert(SqList *L, int x)
{
	int low = 0;
	int high = L -> length - 1;
	int mid;

	while (low <= high)//注意循环的条件
	{
		mid = (low + high)/2;

		if (L -> elem_array[mid] == x)
			break;

		else if (L -> elem_array[mid] < x)
			low = mid + 1;
		else
			high = mid - 1;
	}

//下面两个if只会执行一个
	if (L -> elem_array[mid] == x && mid != L -> length -1)//找到元素而且不是最后一个置换直接后继的元素
	{
		int tmp = L -> elem_array[mid];
		L -> elem_array[mid] = L -> elem_array[mid + 1];
		L -> elem_array[mid + 1] = tmp;
	}

	if (low > high)
	{
		for (int i = L -> length -1 ;i > high ; i--)
		{
			L -> elem_array[i+1] = L -> elem_array[i];
		}

		L -> elem_array[high] = x;
		L -> length = L -> length + 1;
	}
	
		
}